lib/Mi manual de algoritmos/version_world_finals_2009/src/geometria/line_line_intersection.cpp

   1 /*
   2   Finds the intersection between two lines (Not segments!
   3   Infinite lines)
   4   Line 1 passes through points (x0, y0) and (x1, y1).
   5   Line 2 passes through points (x2, y2) and (x3, y3).
   6
   7   Handles the case when the 2 lines are the same (infinite
   8   intersections),
   9   parallel (no intersection) or only one intersection.
  10 */
  11 void line_line_intersection(double x0, double y0,
  12                             double x1, double y1,
  13
  14                             double x2, double y2,
  15                             double x3, double y3){
  16 #ifndef EPS
  17 #define EPS 1e-9
  18 #endif
  19
  20   double t0 = (y3-y2)*(x0-x2)-(x3-x2)*(y0-y2);
  21   double t1 = (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
  22   double det = (y1-y0)*(x3-x2)-(y3-y2)*(x1-x0);
  23   if (fabs(det) < EPS){
  24     //parallel
  25     if (fabs(t0) < EPS || fabs(t1) < EPS){
  26       //same line
  27       printf("LINE\n");
  28     }else{
  29       //just parallel
  30       printf("NONE\n");
  31     }
  32   }else{
  33     t0 /= det;
  34     t1 /= det;
  35     double x = x0 + t0*(x1-x0);
  36     double y = y0 + t0*(y1-y0);
  37     //intersection is point (x, y)
  38     printf("POINT %.2lf %.2lf\n", x, y);
  39   }
  40 }